package demo.DataStrucAndAlgo.Graph;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/30-07-30-16:09
 * @Description：demo.DataStrucAndAlgo.Graph    图的深度优先遍历DFS
 */
/*
DFS
    先访问当前顶点，并输出。按照邻接矩阵查找当前顶点的下一个顶点
    ，当该顶点满足当前顶点与该顶点直接相连且该结点没有被访问过
    则进行递归，新递归中该顶点成为当前顶点，并重复上述操作，
    不满足时，当前顶点将跨过该顶点，寻找下一个可以访问的顶点
    直到找完所有顶点后跳出递归
 */
public class Graph_DFS {
    private ArrayList<Character> vertexList;
    private int[][] edges;
    private int numOfEdge;
    private boolean[] isVisited;     //用于判断顶点是否被访问过
    public Graph_DFS(int num){
        vertexList = new ArrayList<>(num);
        edges = new int[num][num];
        numOfEdge = 0;
        isVisited = new boolean[num];
    }

    /**
     * 深度优先遍历（回溯算法 ）
     * @param n   每次递归中要进行操作的顶点索引
     */
    public void DFS(int n){
        if(n == getNumOfVertex()){
            return;
        }
        isVisited[n] = true;
        System.out.print((char)getVertexByIndex(n) + " -> ");
        for(int i = 0; i < edges[n].length; i++){
            if(edges[n][i] != 0 && !isVisited[i]){
                DFS(i);
            }
        }
    }

    public void insertVertex(char vertex){
        vertexList.add(vertex);
    }

    /**
     * 无向图
     * @param v1       顶点1
     * @param v2     顶点2
     * @param weight    权值
     */
    public void insertEdges(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdge++;
    }
    public int getNumOfVertex(){
        return vertexList.size();
    }
    public int getNumOfEdge(){
        return numOfEdge;
    }
    public int getVertexByIndex(int index){
        return vertexList.get(index);
    }
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    public void show(){
        for (int i = 0; i < edges.length; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }

    public static void main(String[] args) {
        Graph_DFS graph = new Graph_DFS(5);
        for (int i = 0; i < 5; i++) {
            graph.insertVertex((char)('A' + i));
        }
        //添加边：A-B,A-C,C-B,B-E,B-D
        graph.insertEdges(0,1,1);
        graph.insertEdges(0,2,1);
        graph.insertEdges(2,1,1);
        graph.insertEdges(1,4,1);
        graph.insertEdges(1,3,1);
        System.out.println("邻结矩阵为：");
        graph.show();
        System.out.println("A-B边权值为：");
        System.out.println(graph.getWeight(0,1));
        System.out.println("D顶点的数据为：" + (char)graph.getVertexByIndex(3));
        System.out.println("含有的边数位：" + graph.getNumOfEdge());
        System.out.println("-----------------------");
        graph.DFS(3);
    }
}
